import collections
import heapq


class Solution(object):
    def longestPath(self, parent, s):
        self.max_val = 1
        d = collections.defaultdict(set)
        for u, v in enumerate(parent):
            d[v].add(u)

        def dfs(node):
            st = []
            for v in d[node]:
                next_val = dfs(v)
                if s[v] != s[node]:
                    if len(st) < 2:
                        heapq.heappush(st, next_val)
                    else:
                        if next_val > st[0]:
                            heapq.heapreplace(st, next_val)
            if len(st) == 2:
                self.max_val = max(self.max_val, st[0] + st[1] + 1)
                return 1 + st[1]
            else:
                if len(st) == 1:
                    self.max_val = max(self.max_val, st[0] + 1)
                    return 1 + st[0]
                else:
                    return 1

        dfs(0)
        return self.max_val


data = Solution()
parent = [-1, 0, 0, 1, 1, 2]
s = "abacbe"
print(data.longestPath(parent, s))
